﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SAI
{
    class OldBFSTilePuzzle
    {
        /*
        private static void BfsTilePuzzle()
        {
            int dimension = 4;
            int[][] startArr = new int[dimension][];
            int[][] goalArr = new int[dimension][];
            startArr[0] = new int[]{6,5,2,4};
            startArr[1] = new int[]{10,14,3,8};
            startArr[2] = new int[]{13,7,15,11};
            startArr[3] = new int[]{1,9,0,12};
            for (int i = 0,x=0; i < dimension; i++)
            {
                goalArr[i] = new int[dimension];
                for (int j = 0; j < dimension; j++)
                    goalArr[i][j] = ++x;   
            }
            goalArr[dimension - 1][dimension - 1] = 0;
            goalArr[dimension - 1][dimension - 2] = 15;

            int x = 0;
            for (int i = 0; i < dimension; i++)
            {
                startArr[i] = new int[dimension];
                goalArr[i] = new int[dimension];
                for (int j = 0; j < dimension; j++)
                {
                    startArr[i][j] = x++;
                    goalArr[i][j] = i * dimension + j + 1;
                }
            }
            goalArr[dimension - 1][dimension - 1] = 0;
            goalArr[dimension - 1][dimension - 2] = 15;

            // test 1
            startArr[0][0] = 0;
            startArr[1][0] = 1;
            startArr[2][0] = 5;
            startArr[3][0] = 9;
            startArr[3][1] = 13;
            startArr[3][2] = 14;
            startArr[3][3] = 15;


            PuzzleState startState = new PuzzleState(startArr);
            PuzzleState goalState = new PuzzleState(goalArr);
            TilePuzzleNode start = new TilePuzzleNode(startState);
            TilePuzzleNode goal = new TilePuzzleNode(goalState);
            TilePuzzleNode.AllStates.Add(TilePuzzleNode.arrToString(startArr),start);
            TilePuzzleNode.AllStates.Add(TilePuzzleNode.arrToString(goalArr),goal);
            start.printNode();
            goal.printNode();
            Node res = BFS.search(start, goal);
            TilePuzzleNode result = (TilePuzzleNode)res;
            result.printPath();
        }

        private static void build15Puzzle()
        {
            List<PuzzleState> states = new List<PuzzleState>();
            List<int> firstState = new List<int>();
            for (int i = 1; i < 16; i++)
                firstState.Add(i);
            firstState.Add(0);
         //   PuzzleState first = new PuzzleState(firstState);
           // states = findAllStates(first);
            Console.WriteLine("number of states is: " + states.Count);
        }

        private static List<PuzzleState> findAllStates(PuzzleState first)
        {
            return findAllStates(first,new List<PuzzleState>());    
        }
  
        private static List<PuzzleState> findAllStates(PuzzleState curState, List<PuzzleState> list)
        {
            if (contains(list, curState))
                return list;
            list.Add(curState);
            int dimension = curState.Dimension;
            int ind = findZero(curState);
            int row = ind / dimension;
            int col = ind % dimension;
            PuzzleState tmp = null;
            if (col < dimension - 1)
            {
                tmp = getNewState(curState, ind, ind + 1);
                List<PuzzleState> states1 = findAllStates(tmp, list);
                list = mergeLists(states1, list);
            }
            if (col > 0)
            {
                tmp = getNewState(curState, ind, ind - 1);
                List<PuzzleState> states1 = findAllStates(tmp, list);
                list = mergeLists(states1, list);
            }
            if (row < dimension - 1)
            {
                tmp = getNewState(curState, ind, ind + dimension);
                List<PuzzleState> states1 = findAllStates(tmp, list);
                list = mergeLists(states1, list);
            }
            if (row > 0)
            {
                tmp = getNewState(curState, ind, ind - dimension);
                List<PuzzleState> states1 = findAllStates(tmp, list);
                list = mergeLists(states1, list);
            }
            return list;
        }

        private static int findZero(PuzzleState first)
        {
            List<int> state = first.State;
            for (int i = 0; i < state.Count; i++)
                if (state[i] == 0)
                    return i;
            return -1;
        }


        private static void test()
        {
            List<Node> g = buildGraph();
            Node path = BFS.search(g[0], g[1]);
            printPath(path);
            Console.WriteLine("finished");
        }

        private static void printPath(Node path)
        {
            while (path != null)
            {
                if (path.Parent == null)
                    Console.Write(path.ID);
                else
                    Console.Write(path.ID + "<-");
                path = path.Parent;
            }
            Console.WriteLine();
        }
        
                private static List<Node> buildGraph()
                {
                    Node s = new Node("s");
                    Node a = new Node("a");
                    Node b = new Node("b");
                    Node c = new Node("c");
                    Node d = new Node("d");
                    Node e = new Node("e");
                    Node f = new Node("f");

                    s.addOutEdge(a);
                    s.addOutEdge(d);
                    a.addOutEdge(c);
                    a.addOutEdge(b);
                    b.addOutEdge(f);
                    c.addOutEdge(b);
                    d.addOutEdge(e);
                    e.addOutEdge(s);
                    e.addOutEdge(f);
                    f.addOutEdge(e);


                    List<Node> graph = new List<Node>();
                    graph.Add(s);
            
                    //graph.Add(a);
                    //graph.Add(b);
                    //graph.Add(c);
                    //graph.Add(d);
                    //graph.Add(e);
             
                    graph.Add(f);
                    return graph;

                }

                private static PuzzleState getNewState(PuzzleState curState, int ind1, int ind2)
                {
                    List<int> oldState = curState.State;
                    List<int> newState = new List<int>();
                    for (int i = 0; i < oldState.Count; i++ )
                        newState.Add(oldState[i]);
                    newState[ind1] = newState[ind2];
                    newState[ind2] = 0;
                    return new PuzzleState(newState);
                }

                private static List<PuzzleState> mergeLists(List<PuzzleState> states, List<PuzzleState> list)
                {
                    foreach (PuzzleState state in states)
                    {
                        if (!contains(list,state))
                            list.Add(state);
                    }
                    return list;
                }

                private static bool contains(List<PuzzleState> list, PuzzleState tmp)
                {
                    foreach (PuzzleState state in list)
                        if (state.compare(tmp))
                            return true;
                    return false;
                }*/
    }
}
